一、數(shù)據(jù)結構
1、概述

數(shù)據(jù)結構（data structure）：是計算機專業(yè)一門獨立學科，主要研究數(shù)據(jù)的邏輯結構、存貯結構以及數(shù)據(jù)之間的關系

什么是數(shù)據(jù)：

? ? 在計算機系統(tǒng)中，各種字母和數(shù)字符號的組合、語音、圖形、圖像等統(tǒng)稱為數(shù)據(jù)
? ? 又指所有能輸入計算機并且被計算機程序處理的符號的總稱，是用于輸入計算機進行處理，具有一定意義的數(shù)字、字母、符號和模擬量的統(tǒng)稱

2、數(shù)據(jù)結構
1.邏輯結構

? ? 集合

一個存放數(shù)據(jù)的容器，數(shù)據(jù)元素間沒有任何關系

? ? 線性結構

數(shù)據(jù)元素間有線性關系，分為線性表、隊列、棧和串

線型關系：除第一個元素外，其他元素有且只有一個前驅，除最后一個元素外，其他元素有且只有一個后繼

? ? 樹結構

數(shù)據(jù)元素間有層狀關系，例如二叉樹

? ? 圖結構

數(shù)據(jù)元素間有網(wǎng)狀關系
2.存儲結構

? ? 順序存儲結構

數(shù)據(jù)存放在磁盤連續(xù)的空間中

? ? 鏈式存儲結構

數(shù)據(jù)存放在磁盤的任何位置，單向鏈式存貯（單鏈表）、雙向鏈式存貯（雙鏈表）、循環(huán)鏈式存貯（循環(huán)鏈表）
3、線性結構
1、線性表

基于數(shù)組實現(xiàn)線性結構 ，用數(shù)組存放數(shù)據(jù)，并保持元素之間是一個線性關系

編寫線性結構的數(shù)據(jù)結構：
public void insert(int i,Object data); ?// 添加到線性表指定的位置;
public void append(Object data); ?// 追加到線性表的末尾;
public void remove(int i); ?// 移除元素
public void update(int i,Object data); ?// i為下標 ；
public Object get(int i); ?// 獲取元素
public Object[] list();
public int size(); ?// 線性表元素數(shù)量;
public boolean isEmpty(); ?// 線性表是否為空;

public void insert(int i,Object data); ?// 添加到線性表指定的位置;
public void append(Object data); ?// 追加到線性表的末尾;
public void remove(int i); ?// 移除元素
public void update(int i,Object data); ?// i為下標 ；
public Object get(int i); ?// 獲取元素
public Object[] list();
public int size(); ?// 線性表元素數(shù)量;
public boolean isEmpty(); ?// 線性表是否為空;

public void insert(int i,Object data); ?// 添加到線性表指定的位置;
public void append(Object data); ?// 追加到線性表的末尾;
public void remove(int i); ?// 移除元素
public void update(int i,Object data); ?// i為下標 ；
public Object get(int i); ?// 獲取元素
public Object[] list();
public int size(); ?// 線性表元素數(shù)量;
public boolean isEmpty(); ?// 線性表是否為空;

boolean offer(E e); ?// 添加數(shù)據(jù)
Object poll(); ? // 刪除出隊
Object peek(); ?// 返回隊列第一次元素（不刪）
int size(); ?// 元素數(shù)量
boolean isEmpty(); ?// 判斷隊列是否為空

4、串

串：即字符串（String），是由零個或多個字符組成的有限序列。一般表示為s=“c1,c2,c3...cn”

子串：串中任意個連續(xù)的字符組成的子序列

主串：包含子串的串

空串：n=0的串

空格串：值為空格的串
4、樹結構

樹是一種非線性的數(shù)據(jù)結構，由n（n>0）個有限結點組成的具有層次關系的集合。

樹有一個特殊的結點，叫根結點，根結點沒有前驅結點。

樹形結構中，子樹之間不能有交集。

樹的性質如下：

? ? 每個子樹有且只有一個前驅結點
? ? 每個子樹的根結點可以有0或多個后繼結點
? ? 數(shù)是遞歸的
? ? 一個n個結點的數(shù)有n-1條邊

5、圖結構

圖結構是比線性表和樹結構更為復雜的數(shù)據(jù)結構。

樹結構中，子樹之間不能有交集，但在圖結構中，是可以有交集的。

圖結構中有頂點和邊

頂點：圖中的數(shù)據(jù)元素

邊：圖中連接頂點的線

所有的頂點組成一個頂點集合，所有的邊組成一個邊集合，組合在一起就是一個圖結構

無向圖：在一個圖中，如果所有的邊都沒有方向，則稱之為無向圖

有向圖：在一個圖中，邊有方向，則稱之為有向圖

混合圖：一個圖中，邊同時有有向和無向的圖